package com.future;

import com.future.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Description: 437. 路径总和 III
 * <p>
 * [1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]
 * 0
 *
 * @author weiruibai.vendor
 * Date: 2023/1/9 10:11
 */
public class Solution_437 {

    private static Solution_437 instance = new Solution_437();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);

        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(1);

        root.right = new TreeNode(-3);
        root.right.right = new TreeNode(11);
        int targetSum = 8;
        int i = instance.pathSum(root, targetSum);
        System.out.println(i);
    }

    public int pathSum(TreeNode root, int targetSum) {
        List<Long> list = new LinkedList<>();
        calcPathSum(root, list, targetSum);
        return ans;
    }

    int ans = 0;

    private void calcPathSum(TreeNode root, List<Long> list, int target) {
        if (root == null) {
            return;
        }
        int val = root.val;
        List<Long> newList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            Long tmp = list.get(i) + val;
            if (tmp >= Integer.MAX_VALUE || tmp <= Integer.MIN_VALUE) continue;// 注意！！
            if (tmp.intValue() == target) {
                ans++;
            }
            newList.add(tmp);
        }
        newList.add(Long.valueOf(val));
        if (val == target) {
            ans++;
        }
        calcPathSum(root.left, newList, target);
        calcPathSum(root.right, newList, target);
    }


}
